#pragma once


#include <string>
#include <algorithm>
#include <functional>
#include <vector>
//#define NEWS_BENCHMARK 1
#include "NewsBenchMark.h"

struct PointEntry
{
    char* point;
    int   level;

    PointEntry( char* p, int l ){ point = p; level = l; }
    PointEntry(){ point = 0; level = 0; }
    int  Compare( const PointEntry& val ) const{ return (int)(point - val.point); }
    bool operator ==( const PointEntry& val){ return ( Compare(val) == 0); }
};

//The cache used to cache buf pointer and the level, transparent for client
class XMLNodeCache
{
public:
    typedef PointEntry                  record_type;
    typedef std::vector<record_type>    array_type;
    typedef array_type::iterator        iterator;
    typedef array_type::const_iterator  const_iterator;
    typedef array_type::size_type       size_type;
    enum err_code{
        err_ok = 0,
        err_build_cache,
        err_node_na,
        err_next,
        err_invalid = 64
    };
private:
    array_type m_entries;

public:
    //Init the cache entries, clear them for further use
    void            Init(){  m_entries.clear(); }
    size_type       Size(){ return m_entries.size(); }

    err_code        GetHint( char* p, int curLevel, int minTarLv, int maxTarLv, int minFailLv, int maxFailLv, char*& outp, int& outl, bool forward = true )
    {
        err_code    ret = err_ok;
        iterator    it;
        record_type key( p, 0);
        ret = LocateRecord( key, it );

        switch( ret )
        {
        case err_node_na:
            return err_node_na;
        case err_next:
            if( Size() > 0 )
            {   
                if( forward)
                {
                    key = m_entries.back();
                    outp = key.point;
                    outl = key.level;
                    return err_build_cache;
                }
                else{
                    return err_node_na;
                }
            }
            else
            {
                return err_build_cache;
            }

        case err_ok:
            int step = forward? 1 : -1;
            iterator end = forward? m_entries.end(): m_entries.begin();
            //We get the record
            //Move to the next node
            it += step;

            for( ; it != end; it += step )
            {
                int level = it->level;
                if( maxFailLv == -1 )
                    maxFailLv = 65535; 
                if( maxTarLv == -1 )
                    maxTarLv = 65535;

                if( level >= minFailLv && level <= maxFailLv )
                {
                    //we should return na
                    return err_node_na;
                }
                if( level >= minTarLv && level <= maxTarLv )
                {
                    outp = it->point;
                    outl = level;
                    return err_ok;
                }

            }
            if( forward )
            {
                //We met the last one and we should build the cache from the point
                it -= step;
                outp = it->point;
                outl = it->level;
                return err_build_cache;
            }
            return err_node_na;
        }
        return err_node_na;

    }

    err_code        PushBack( const record_type& val )
    {
        if( m_entries.size() == 0 || val.Compare( m_entries.back() ) > 0 )
            m_entries.push_back( val ); 
        return err_ok;
    }

    err_code        InsertAndFix( const record_type& val ) //Means we insert the val, if the val already exist, then use the current value to fix the cache's level
    {
        iterator    pos;
        switch( LocateRecord(val, pos) )
        {
        case err_next:
            m_entries.push_back( val );
            break;
        case err_node_na:
            m_entries.insert( pos, val );
            break;
        case err_ok:
            *pos = val;
            break;
        }
    }
    err_code        LocateRecord( const record_type& val, iterator& pos )
    {
        //Find the record, if exist then return err_ok,
        //If not exist, then return err_node_na
        int res;

        if( Size() > 0 )
        {
            iterator l = m_entries.begin();
            //Since the vector is pre ordered, lower to upper, then
            //we can use binary search
            iterator r = m_entries.end() - 1;

            if( r->point < val.point )
                return err_next;

            iterator m;

            while( (r - l)  > 4)
            {
                m = l + ( r - l )/2;

                res = val.Compare(*m);

                if( res > 0 )
                {
                    l = m;
                    continue;
                }
                if( res < 0 )
                {
                    r = m;
                    continue;
                }
                l = r = m;
                break;
            }
            if( l == r )
            {
                if( val.Compare(*l) == 0 )
                {
                    pos = l;
                    return err_ok;
                }else{
                    //We find the wrong code
                    pos = l;
                    return err_node_na;
                }
            }
            for( ; l <= r; ++l )
            {
                int res = val.Compare(*l);

                if( res == 0 )
                {
                    pos = l;
                    return err_ok;
                }
                else if( res > 0 )
                {
                    pos = l;
                }
                else if( res < 0 )
                {
                    return err_node_na;
                }
            }
            return err_next;
        }else{
            return err_next;
        }
    }


    err_code        RetrieveRecord( record_type& val )
    {
        iterator pos;
        err_code ret = LocateRecord( val, pos );
        switch( ret )
        {
        case err_ok:
            val.level = pos->level;
            return err_ok;
        case err_next:
            return err_next;
        case err_node_na:
            return err_node_na;
        default:
            return err_node_na;
        }
    }
    //The following support the iterator function
    record_type&    front()
    {

        return m_entries.front();
    }

    record_type&    back()
    {
        return m_entries.back();
    }

    iterator        begin()
    {
        return m_entries.begin();
    }
    iterator        end()
    {
        return m_entries.end();
    }


    //Indicate whether p is under cache coverage
    bool            InRange( char* p )
    {
        if( m_entries.size() > 0 )
        {
            return p <= m_entries.back().point;
        }
        //if the size is 0, it is ready for anything.
        return true;
    }
};